package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/7 12:23
 * @description：https://leetcode-cn.com/problems/coloring-a-border/
 */
public class 边界着色 {
    @Test
    public void test() {
        Solution solution = new Solution();
        int[][] nums = solution.colorBorder(new int[][]{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}, 1, 1, 2);
        for (int[] num : nums) {
            System.out.println(Arrays.toString(num));
        }
        
    }

    class Solution {
        private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        private int[][] map;
        private boolean[][] isVisited;
        private int num;

        public int[][] colorBorder(int[][] grid, int row, int col, int color) {
            this.map = grid;
            this.isVisited = new boolean[grid.length][grid[0].length];
            isVisited[row][col] = true;
            this.num = map[row][col];
            dfs(row, col, color);
            return grid;
        }

        private void dfs(int row, int col, int color) {
            for (int i = 0; i < dirs.length; i++) {
                int curRow = row + dirs[i][0];
                int curCol = col + dirs[i][1];
                if (curRow >= 0 && curRow < map.length
                        && curCol >= 0 && curCol < map[0].length
                        && !isVisited[curRow][curCol]
                        && map[curRow][curCol] == num) {
                    boolean isOk = true;
                    for (int j = 0; j < dirs.length; j++) {
                        int cur_Row = curRow + dirs[j][0];
                        int cur_Col = curCol + dirs[j][1];
                        if (cur_Row >= 0 && cur_Row < map.length
                                && cur_Col >= 0 && cur_Col < map[0].length) {
                            if (map[cur_Row][cur_Col] != num) {
                                isOk = false;
                                break;
                            }
                        }
                    }
                    if (!isOk) {
                        map[curRow][curCol] = color;
                    }
                    isVisited[curRow][curCol] = true;
                    dfs(curRow, curCol, color);
                }
            }
        }
    }

}
